import java.util.Deque;
import java.util.LinkedList;

class Solution3 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        int num = 0;
        if(nums.length == 0 || k == 0) return new int[0];
        Mydeque mydeque = new Mydeque();
        for (int i=0; i<k; i++) {
            mydeque.add(nums[i]);
        }
        res[num++] = mydeque.peek();
        for(int i=k; i<nums.length; i++) {
            mydeque.poll(nums[i-k]);
            mydeque.add(nums[i]);
            res[num++] = mydeque.peek();
        }
        return res;
    }
}
class Mydeque {
    Deque<Integer> deque = new LinkedList<>();
    public void poll(int val) {
        if(!deque.isEmpty() && deque.peekFirst() == val) {
            deque.poll();
        }
    }
    public void add(int val) {
        while(!deque.isEmpty() && deque.peekLast() < val) {
            deque.pollLast();
        }
        deque.addLast(val);
    }
    public int peek(){
        return deque.peek();
    }
}